|
In graph theory, an eternal dominating set for a graph ''G'' = (''V'', ''E'') is a subset ''D'' of ''V'' such that ''D'' is a dominating set on which mobile guards are initially located (at most one guard may be located on any vertex). The set ''D'' must be such that for any infinite sequence of attacks occurring sequentially at vertices, the set ''D'' can be modified by moving a guard from an adjacent vertex to the attacked vertex, provided the attacked vertex has no guard on it at the time it is attacked. The configuration of guards after each attack must induce a dominating set. The eternal domination number, ''γ''∞(''G''), is the minimum number of vertices possible in the initial set ''D''. For example, the eternal domination number of the cycle on five vertices is three. The eternal dominating set problem, also known as the eternal domination problem and the eternal security problem, can also be interpreted as a combinatorial game played between two players that alternate turns: a defender, who chooses the initial dominating set ''D'' and the guard to send to each attack that occurs at a vertex without a guard; and an attacker, who chooses the vertex to be attacked on their turn. The attacker wins the game if they can ever choose a vertex to be attacked such that there is no guard on that vertex or a neighboring vertex; the defender wins otherwise. In other words, the attacker wins the game if they can ever attack a vertex such that the attack cannot be defended. As noted in , the eternal dominating set problem is related to the ''k''-server problem in computer science. ==History== Motivated by ancient problems in military defense described in the series of papers , , , and , the eternal domination problem was initially described in 2004 in a paper by . That was followed by the publication of a paper on eternal domination by , which also introduced a variation on the problem called ''m''-eternal domination in which all of the guards are allowed to move to adjacent vertices, if they so desire, in response to an attack, so long as one guard moves to the attacked vertex (assuming there was not a guard on the attacked vertex, otherwise no guard needs to move). Subsequent to the paper, a number of papers by other authors appeared in the mathematical literature. In these subsequent papers, several additional variations on the eternal domination problem were proposed including the eternal vertex cover problem, the eternal independent set problem, eternal total dominating sets, eternal connected dominating sets, and eternal dominating sets in the eviction model (the latter model requires that when attacks occur a vertex with a guard and the guard must move to a neighboring vertex that contains no guard, if one exists). A survey paper describing many of the results on the eternal domination problem and many of the variations of the problem can be found at . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Eternal dominating set」の詳細全文を読む スポンサード リンク
|